package P628_三个数最大乘积;

import java.util.Arrays;

/**
 * 注意 0 还有负数
 */
public class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int ret = Integer.MIN_VALUE;
        if (len > 6) {
            nums = new int[]{nums[0], nums[1], nums[2], nums[len - 1], nums[len - 2], nums[len - 3]};
            len = 6;
        }
        int tmp;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len && j != i; j++) {
                for (int k = 0; k < len && k != i && k != j; k++) {
                    tmp = nums[i] * nums[j] * nums[k];
                    ret = Math.max(ret, tmp);
                }
            }
        }

        return ret;
    }
    public int maximumProduct2(int[] nums){
        Arrays.sort(nums);
        //官方题解。 其实就是最小的两个和最大的三个之间的事情。。 不用考虑0了
        //TODO 可以不用sort（毕竟起码是NLogN),可以直接线性扫描找出这五个数
        return Math.max(nums[0] * nums[1] * nums[nums.length - 1],nums[nums.length -1] * nums[nums.length - 2] * nums[nums.length-3]);
    }
    public static void main(String args[]){
        System.out.println(new P628_三个数最大乘积.Solution().maximumProduct(new int[]{-90,-89,-1,-2,0,0,0,0,4,5}));
    }
}
